#include "TestDijkstra.h"
#include "DijkstraAlgo.h"
#include "MakeGraph.h"

const int NUMBER_OF_TESTS = 100;
const int MAX_SIZE = 100;

std::vector<std::vector<int> > StupidDistances(const Graph &graph){
    int vertices_number = graph.GetNumberOfVertices();
    std::vector<std::vector<int> > distances (vertices_number, std::vector<int>(vertices_number));
    for(int from = 0; from < vertices_number; from++){
        for(int to = 0; to < vertices_number; to++){
            distances[from][to] = graph.GetEdgeWeight(from, to);
            if(from == to) distances[from][to] = 0;
        }
    }
    for(int first_vertex = 0; first_vertex < vertices_number; first_vertex++){
        for(int second_vertex = 0; second_vertex < vertices_number; second_vertex++){
            for(int third_vertex = 0; third_vertex < vertices_number; third_vertex++){
                distances[second_vertex][third_vertex] = std::min(distances[second_vertex][third_vertex], 
                        distances[second_vertex][first_vertex] + distances[first_vertex][third_vertex]);
            }
        }
    }
    return distances;
}

void TestDistances(){
    for(int test = 0; test < NUMBER_OF_TESTS; test++){
        int vertices_number = rand() % MAX_SIZE;
        std::vector<edge> edges = MakeRandomEdges(vertices_number);
        std::auto_ptr<Graph> graph = MakeCompactGraph(vertices_number, edges);
        std::vector<std::vector<int> > got_distances (vertices_number, std::vector<int>(vertices_number));
        for(int vertex = 0; vertex < vertices_number; vertex++){
            DijkstraAlgo tester (*graph, vertex);
            got_distances[vertex] = tester.GetDistances();
        }
        std::vector<std::vector<int> > right_distances = StupidDistances(*graph);
        for(int from = 0; from < vertices_number;from++){
            for(int to = 0; to < vertices_number; to++){
                if(got_distances[from][to] != right_distances[from][to]){
                    throw std::logic_error("DijkstraAlgo.GetDistances ERROR : wrong answer");
                }
            }
        }
    }
}

//const навесить не получилось, поскольку вызываем DijkstraAlgo (Graph& graph, int start_vertex)
void CheckFindOptimalPath(Graph& graph, int begin){
    DijkstraAlgo check_path (graph, begin);
    for(int end = 0; end < graph.GetNumberOfVertices(); end++){
        if(check_path.GetDistances()[end] == INFINITY){
            if(check_path.FindOptimalPath(end).size() != 0){
                throw std::logic_error("DijkstraAlgo.FindOptimalPath ERROR : wrong answer begin end");
            }
            else{
                continue;
            }
        }
        std::vector<int> got_path = check_path.FindOptimalPath(end);
        if(got_path[0] != begin || got_path[got_path.size() - 1] != end){
            throw std::logic_error("DijkstraAlgo.FindOptimalPath ERROR : wrong answer begin end");
        }
        int distance = check_path.GetDistances()[end];
        int path_distance = 0;
        for(int path_index = 0; path_index < got_path.size() - 1; path_index++){
            int from = got_path[path_index];
            int to = got_path[path_index + 1];
            if(graph.GetEdgeWeight(from, to) == INFINITY){
                path_distance = INFINITY;
                break;
            }
            path_distance += graph.GetEdgeWeight(from, to);
        }
        if(distance != path_distance){
            throw std::logic_error("DijkstraAlgo.FindOptimalPath ERROR : wrong answer sum");
        }
    }
}


void TestFindOptimalPath(){
    for(int test = 0; test < NUMBER_OF_TESTS; test++){
        int vertices_number = rand() % MAX_SIZE;
        std::vector<edge> edges = MakeRandomEdges(vertices_number);
        std::auto_ptr<Graph> graph = MakeCompactGraph(vertices_number, edges);
        for(int begin = 0; begin < vertices_number; begin++){
            CheckFindOptimalPath(*graph, begin);
        }
    }
}




void TestAllDijkstra(){
    TestDistances();
    TestFindOptimalPath();
}
